1. Field of the Invention
The present invention relates to a packet scheduling system and method, and more particularly, to a packet scheduling system and method capable of fair link resource distribution among a plurality of sessions requesting transmissions to an identical output link in input and output interfaces of a node, such as an asynchronous transfer mode (ATM) switch or a router, in a high-speed packet exchange network such as an ATM network or the Internet.
2. Description of the Related Art
Generally, packet scheduling algorithms are broken down into two methods according to operation modes of a server: one is a work-conserving method, by which the server provides services continuously unless there are no waiting packets in a queue, and the other is a non work-conserving method by which the server does not provide services and maintains a waiting state if predetermined conditions are not satisfied even though there is a packet waiting for services in a queue. In the latter method, though there is a waiting packet the server does not provide services such that the utilization efficiency of the server is relatively low but performance requirements determined in advance, such as a delay bound or a delay jitter limit, can be accurately guaranteed. Meanwhile, in the former method, the utilization efficiency of the server is higher but a minimum performance for each session should be guaranteed irrespective of the operations of other sessions and a mechanism capable of fair distribution of a contract speed for each session and the like for a plurality of requests to use idle resources of the server should be considered.
A theory underlying the work-conserving method is a generalized processor sharing (GPS) algorithm disclosed in an article by Abhay K. Parekh and Robert G. Gallager, “A generalized processor sharing approach to flow control in integrated services networks: The single node case” vol. 1, pp. 344-357, IEEE/ACM Transactions on Networking, June 1993. The article provides a hypothetical theory in which all input traffic is modeled as a flow of fluid and a server is used as a scheduling system that provides services at the same time to all links requesting services so that idealistic fairness and optimal delay bound values are provided. However, since the minimum unit of traffic is a packet in an actual packet network environment and a server can transmit only one packet at a time, it is impossible to actually implement the system suggested in the article and the article is only providing conceptual performance criteria which all process scheduling algorithms aim at.
As one of the algorithms that are implemented in actual network environments, closest to the concept of the GPS algorithm described above, there is a weighted fair queueing (WFQ) which assumes that a basic unit of ingress traffic is a packet. The WFQ algorithm introduces a concept of virtual time for displaying the operation state of a GPS server because the operation of the GPS server should be imitated as if traffic modeled as the flow of fluid are all serviced at the same time. A system virtual time is updated with the amount of work performed in the GPS server in each event occurring on the GPS system, such as arrival of a new packet or departure of a packet being serviced. The updated virtual finish time is used as a time stamp of a packet. This algorithm can provide performance close to the GPS algorithm, but in the worst case, while one packet is being transmitted, new packets from all links may arrive such that calculation and update of the virtual time may be repeated with the same frequency as the number of the links. Accordingly, it is actually difficult to implement the algorithm in a high-speed network environment requiring high-speed determination of transmission order of packets.
In a scheduling algorithm which was suggested to improve the WFQ algorithm with this complexity-to-implement problem, there is a self clocked fair queueing (SCFQ) algorithm. Unlike the WFQ algorithm, this algorithm does not have the continuous GPS simulation step and when a new packet arrives, it regards the time stamp of the packet as a virtual time. As a result, packets which arrived during one transmission share an identical virtual time such that the complexity due to calculation of the virtual time can be greatly reduced. However, in the worst case, when an arbitrary packet arrives, all session can have the time as the time stamp being serviced such that the packet which is newly arrived has to wait until packets of all sessions are transmitted, irrespective of complying with traffic rules. In this case, the waiting time is proportionate to the number of linked sessions. Thus, the SCFQ algorithm improves the complexity due to calculation of the virtual time but degrades the delay bound that can be guaranteed, compared to the WFQ algorithm.
As a method to solve the drawback of the SCFQ algorithm, there is a starting potential fair queueing (SPFQ) algorithm. In the SPFQ algorithm, whenever transmission of a packet finishes, the virtual time is reset to the smallest value among the virtual start time values of packets in the head of each queue. The SPFQ algorithm has an advantage of maintaining good performance but has a disadvantage of an arrangement process for the virtual start time which is additionally needed.
As a method to improve the calculation complexity of the WFQ algorithm with an approach similar to that of the SCFQ algorithm, there is a minimum-delay self-clocked fair queueing (MD-SCFQ) algorithm. As the SCFQ algorithm, the MD-SCFQ algorithm does not have a separate step for simulation of the GPS, and calculates the system virtual time by using information on the front packet waiting in a queue so that it can reduce the complexity of calculation compared to the WFQ algorithm and improve the delay characteristic compared to the SCFQ algorithm. However, this algorithm has a disadvantage of overhead for continuously collecting and managing information on packets waiting in a queue at a time when the system virtual time is calculated.
Thus, the work-conserving type scheduling algorithms have different methods for calculating and maintaining virtual time functions and time stamps for respective systems. In a scheduling system for a high-speed network environment, the most important performance parameter is the simplicity of a system related to high-speed determination of a transmission order. When this is considered, it can be said that the closer to the GPS, a scheduling system can maintain the fairness and delay characteristics that are basic requirements of a work-conserving scheduling system while maintaining this simplicity, the better the scheduling system is. Therefore, a new packet scheduling system and method are needed in which the delay bound and fairness index of the WFQ level can be guaranteed in a switch or a router in a high-speed packet exchange network and the calculation complexity O(1) of the system virtual time can be maintained.